
package ueb14.uebTree;

import ueb14.htw.tree.TreeErrorException;
import ueb14.htw.tree.TreeImpl;

/**
 *
 * @author adier
 */
public class TreeManagment {
    
    private static final int STANDARTSIZE      = 50;
    private static final int CHANGESIZE        = 25;
    private static final int MAXSIZE           = 50;
    private static final int MINSIZE           = 25;
    
    private TreeImpl        rbTree         = null;
    private Professor       professor      = null;
    private Object[]        array          = null;
    private int             actualSize     = -1;
    private int             arraySize      = 0;
    public TreeImpl         root           = null;
    
    
    
    public TreeManagment(String name) throws ProfessorException, TreeErrorException{
        this(name, null, 0);
    }
    
    public TreeManagment(String name, String vorlesung, int salary) throws ProfessorException, TreeErrorException{
        array           = new Object[STANDARTSIZE];
        rbTree          = new TreeImpl(name);
        professor       = new Professor(name, vorlesung, salary);
        arraySize       = STANDARTSIZE;
        array[0]        = professor;
        actualSize++;
        rbTree.setName(name);
        rbTree.setReference(professor);
        rbTree.setRightChild(new TreeImpl());
        rbTree.setLeftChild(new TreeImpl());
        root = rbTree;
    }
    
    public void add(String name) throws ProfessorException, TreeErrorException, TreeManagmentException{
        add(name, null, 0);
    }
    
    public void add(String name, String vorlesung, int salary) throws ProfessorException, TreeErrorException, TreeManagmentException{
        if(rbTree == null)
            throw new TreeManagmentException("Tree does not exist");
            
        TreeImpl newTree = rbTree.search(name);
        if(newTree.getName() == null)
        {
            if(freespace() < MINSIZE)
            {
                Object[] newarray = new Object[arraySize + CHANGESIZE];
                arraySize           += CHANGESIZE;
                for(int i = 0; i <= array.length-1; i++)
                {
                    newarray[i] = array[i];
                }
                array = newarray;
                   
            }
            professor         = new Professor(name, vorlesung, salary);
            actualSize++;
            array[actualSize] = professor;
            if(newTree.isRightChild())
            {
                newTree.getParent().setRightChild(newTree);
            }
            else
            {
                newTree.getParent().setLeftChild(newTree);
            }
            newTree.setReference(professor); 
            repairInsertion(rbTree.search(name));
        }
        else
        {
            throw new TreeManagmentException("Element already exists");
        }
  
    }
    
    public void del(String name) throws TreeErrorException, TreeManagmentException{
        if(rbTree == null)
            throw new TreeManagmentException("Tree does not exist");
        
        TreeImpl newTree    = rbTree.search(name);
        int      position   = -1;
        if(newTree.getName() != null)
        {
            if(freespace() > MAXSIZE)
            {
                Object[] newarray = new Object[arraySize - CHANGESIZE];
                arraySize           -= CHANGESIZE;
                for(int i = 0; i <= array.length-1; i++)
                {
                    newarray[i] = array[i];
                }
                array = newarray;
                   
            }
            actualSize--;
            
            for (int i = 0; i <= actualSize; i++)
            {
                if( ( (Professor) array[i]).getName().equals(name))
                {
                    position = i;
                }
            }
            
            for (int i = position; i <= actualSize; i++)
            {
                array[i] = array[i+1];
            }
            
            
            newTree.setReference(null); 
            removeTree(rbTree.search(name));
        }
        else
        {
            throw new TreeManagmentException("Element do not exists");
        }
    }
    
    
    private int freespace(){
        return arraySize - actualSize -1;
    }
    

    
    public void removeTree(TreeImpl treeI) throws TreeErrorException, TreeManagmentException {
        if (treeI == null) {
                throw new TreeManagmentException("Cannot remove null node!");
        }
        if (!(treeI instanceof TreeImpl)) {
                throw new TreeManagmentException("Cannot remove node of another tree!");
        }
        TreeImpl tree = (TreeImpl) treeI;

        if((!(tree.getLeftChild().isNil()))&&(!(tree.getRightChild().isNil())))
        {
                removeTreeTwoChildren(tree);
        }
        else 
        {
                removeTreeOneChild(tree); 
        }

    }
	
	
    public void removeTreeTwoChildren(TreeImpl tree) throws TreeErrorException, TreeManagmentException {
        //should never happen
        assert(((tree.getLeftChild().isNil())) && ((tree.getRightChild().isNil())));

        removeTree(swap(tree.getLeftChild().getMax(),tree)); 	
    }
	
	
	
    public void removeTreeOneChild(TreeImpl tree) throws TreeErrorException {
        TreeImpl x = (TreeImpl) new TreeImpl(tree);
        TreeImpl a = tree.getLeftChild();
        TreeImpl b = tree.getRightChild();

        if(!(tree.isRoot()))
        {
            if(tree.isRightChild())
            {
                tree.getParent().setRightChild(x);
                x.setParent(tree.getParent());
            }
            else
            {
                tree.getParent().setLeftChild(x);
                x.setParent(tree.getParent());
            }
        }
        else
        {
            root=x;
            x.setParent(null);
        }

        if ( !a.isNil() ) {
            x.setName(a.getName());
            x.setReference(a.getReference());
            x.setLeftChild(a.getLeftChild());
            x.setRightChild(a.getRightChild());
        }
        else {
            x.setName(b.getName());
            x.setReference(b.getReference());
            x.setLeftChild(b.getLeftChild());
            x.setRightChild(b.getRightChild());

        }
        if(a.isBlack())
        {
                assert(a.isBlack());
                x.makeBlack();
        }
        else
        {
                x.makeRed();
        }
        if(tree.isRed())
        {
                assert (tree.isRed());
                return;
        }
        if((tree.isBlack()) && (x.isRed()))
        {
                x.makeBlack();
                return;
        }
        if((tree.isBlack()) && (x.isBlack()))
        {
            if(!(x.isRoot()))
            {
                    assert (!(x.isRoot()));
                    if(!(x.getBrother().isNil()))
                    {
                            repairDeletion(x);
                    }
                    /*else
                    {
                            throw new UnsupportedOperationException("Bruder existiert nicht.");
                    }*/
            }
            else
            {
                    repairDeletion(x);
            }

        }
    }


    public TreeImpl swap (TreeImpl toSwap, TreeImpl tree) throws TreeErrorException {
    TreeImpl r= (TreeImpl)new TreeImpl(tree);
    TreeImpl s= (TreeImpl)new TreeImpl(tree);

    TreeImpl x = tree.getLeftChild();
    TreeImpl y = tree.getRightChild();
    if(!(tree.isRoot()))
    {
        assert(!(tree.isRoot()));
        if(tree.isRightChild())
        {
            assert(tree.isRightChild());
            tree.getParent().setRightChild(s);
        }
        else
        {
            tree.getParent().setLeftChild(s);
        }
    }
    else
    {
        root=s;
        s.setParent(null);
    }
    s.setName(toSwap.getName());
    s.setReference(toSwap.getReference());
    s.setLeftChild(x);
    s.setRightChild(y);
    s.setParent(tree.getParent());
    if(toSwap.getLeftChild().isNil())// a
    {
        assert (toSwap.getLeftChild().isNil());
        r.setLeftChild(toSwap.getLeftChild());
    }
    else
    {
        r.setLeftChild(toSwap.getLeftChild());
    }
    if(toSwap.isRightChild())
    {
        assert(toSwap.isRightChild());
        toSwap.getParent().setRightChild(r);
    }
    else
    {     
        toSwap.getParent().setLeftChild(r);
    }

    if(tree.isBlack())
    {
        s.makeBlack();
        assert (s.isBlack());
    }
    else
    {
        s.makeRed();
    }
    if(toSwap.isBlack())
    {
        r.makeBlack();
        assert (r.isBlack());
    }
    else
    {
        r.makeRed();
    }
    r.setRightChild(toSwap.getRightChild());// b 
    r.setParent(toSwap.getParent());
    r.setName(toSwap.getName());
    r.setReference(toSwap.getReference());

    return r;

    }
    
    
    protected void repairDeletion(TreeImpl tree) throws TreeErrorException {
        // case 1
        if (tree.isRed()) {
            repairDeletionCase1(tree);
            return;
        }
        // case 2
        if (tree.isRoot()) {
            repairDeletionCase2(tree);
            return;
        }
        if ((tree.isLeftChild())&&(tree.getBrother().isRed()))//Fall 3a
        {
            repairDeletionCase3a(tree);

        }
        if((tree.isRightChild())&&(tree.getBrother().isRed()))//Fall 3b
        {
            repairDeletionCase3b(tree);
        }
        if(tree.getBrother().isBlack())//Fall 4
        {
            if((tree.getBrother().getLeftChild().isBlack())&&(tree.getBrother().getRightChild().isBlack()))
            {
                repairDeletionCase4(tree);
                return;
            }
        }
        if((tree.isLeftChild())&&(tree.getBrother().getLeftChild().isRed())&&(tree.getBrother().getRightChild().isBlack()))//Fall 5a  
        {
            repairDeletionCase5a(tree);
            return;
        }
        if((tree.isRightChild())&&(tree.getBrother().getRightChild().isRed())&&(tree.getBrother().getLeftChild().isBlack())) //Fall 5b 
        {
            repairDeletionCase5b(tree);	
            return;
        }
        if((tree.isLeftChild())&&(tree.getBrother().isBlack())&&(tree.getBrother().getRightChild().isRed()))//Fall 6a
        {
            repairDeletionCase6a(tree);
            return;
        }
        if((tree.isRightChild())&&(tree.getBrother().isBlack())&&(tree.getBrother().getLeftChild().isRed())) //Fall 6b
        {
            repairDeletionCase6b(tree);
            return;
        }

    }


    protected void repairDeletionCase1(TreeImpl tree) {
            assert tree.isRed();
            tree.makeBlack();
    }


    protected void repairDeletionCase2(TreeImpl tree) {
            assert tree.isRoot();
            // with case 2 do nothing
    }



    protected void repairDeletionCase3a(TreeImpl tree) throws TreeErrorException {
            tree.getParent().makeRed();
            tree.getBrother().makeBlack();
            rotateLeft(tree.getParent());
            return;
    }


    protected void repairDeletionCase3b(TreeImpl tree) throws TreeErrorException {
            tree.getParent().makeRed();
            tree.getBrother().makeBlack();
            rotateRight(tree.getParent());
            return;
    }


    protected void repairDeletionCase4(TreeImpl tree) throws TreeErrorException {
            tree.getBrother().makeRed();
            repairDeletion(tree.getParent()); 

    }


    protected void repairDeletionCase5a(TreeImpl tree) throws TreeErrorException {
            tree.getBrother().getLeftChild().makeBlack();
            tree.getBrother().makeRed();
            rotateRight(tree.getBrother());
            repairDeletion(tree);
    }


    protected void repairDeletionCase5b(TreeImpl tree) throws TreeErrorException {
            tree.getBrother().getRightChild().makeBlack();
            tree.getBrother().makeRed();
            rotateLeft(tree.getBrother());
            repairDeletion(tree);
    }

    /**
        * Repair deletion case 6a.
        * 
        * @param tree
        *            The node that replaces the deleted node as specified in the
        *            documentation.
        */
    protected void repairDeletionCase6a(TreeImpl tree) throws TreeErrorException {
            if(tree.getParent().isBlack())
            {
                    tree.getBrother().makeBlack();
            }
            else
            {
                    tree.getBrother().makeRed();
            }
            tree.getParent().makeBlack();
            tree.getBrother().getRightChild().makeBlack();
            rotateLeft(tree.getParent());
            return;
    }


    protected void repairDeletionCase6b(TreeImpl node) throws TreeErrorException {
            if(node.getParent().isBlack())
            {
                    node.getBrother().makeBlack();
            }
            else
            {
                    node.getBrother().makeRed();
            }
            node.getParent().makeBlack();
            node.getBrother().getLeftChild().makeBlack();
            rotateRight(node.getParent());
            return;
    }


    protected void repairInsertion(TreeImpl node) throws TreeErrorException {
            // case 1
            if (node.isRoot()) //Fall 1
            {
                    repairInsertionCase1(node);
                    return;
            }
            if(node.getParent().isBlack()==true)//Fall 2
            {
                    repairInsertionCase2(node);
                    return;
            }
            if((node.getParent().isBlack()==false)&&(node.getUncle().isBlack()==false))//Fall 3
            {
                    repairInsertionCase3(node);
                    return;
            }
            if((node.getUncle().isBlack()==true)&&(node.getParent().isLeftChild()))//Fall 4
            {
                    repairInsertionCase4(node);
                    return;
            }
            if((node.getUncle().isBlack()==true)&&(node.getParent()==node.getGrantParent().getRightChild()))//Fall 5
            {
                    repairInsertionCase5(node);
                    return;
            }
    }


    protected void repairInsertionCase1(TreeImpl tree) {
            assert tree.isRoot();
            tree.makeBlack();
    }


    protected void repairInsertionCase2(TreeImpl tree) {
            tree.makeRed();
    }


    protected void repairInsertionCase3(TreeImpl tree) throws TreeErrorException {
            tree.makeRed();
            tree.getGrantParent().makeRed();
            tree.getParent().makeBlack();
            tree.getUncle().makeBlack();
            repairInsertion(tree.getGrantParent());
    }


    protected void repairInsertionCase4(TreeImpl node) throws TreeErrorException {
            if(node.isRightChild())
            {
                    assert node.isRightChild();
                    repairInsertionCase4a(node);
                    return;
            }
            else
            {
                    assert node.isLeftChild();
                    repairInsertionCase4b(node);
            }

    }

    protected void repairInsertionCase4a(TreeImpl tree) throws TreeErrorException {
            tree.makeRed();
            rotateLeft(tree.getParent());
            repairInsertionCase4b(tree.getLeftChild());

    }

    protected void repairInsertionCase4b(TreeImpl tree) throws TreeErrorException {
            assert tree.isLeftChild();
            tree.getParent().makeBlack();
            tree.getGrantParent().makeRed();
            tree.makeRed();
            rotateRight(tree.getGrantParent());
    }


    protected void repairInsertionCase5(TreeImpl tree) throws TreeErrorException {
            if(tree.isLeftChild())
            {
                    assert tree.isLeftChild();
                    repairInsertionCase5a(tree);
            }
            else
            {
                    assert tree.isRightChild();
                    repairInsertionCase5b(tree);
            }
    }

    protected void repairInsertionCase5a(TreeImpl tree) throws TreeErrorException {
            rotateRight(tree.getParent());
            tree.makeRed();
            repairInsertionCase5b(tree.getRightChild());
    }

    protected void repairInsertionCase5b(TreeImpl tree) throws TreeErrorException {
            tree.getParent().makeBlack();
            tree.getGrantParent().makeRed();
            tree.makeRed();
            rotateLeft(tree.getGrantParent());
    }

    /**
        * Rotates the subtree of the given tree left around that tree.
        * 
        * @param tree
        *            The tree to rotate around.
        */
    protected void rotateLeft(TreeImpl tree) throws TreeErrorException {

            TreeImpl y  = tree;
            TreeImpl x  = y.getRightChild();
            TreeImpl b  = x.getLeftChild();
            x.setParent(y.getParent());
            if(!(y.isRoot()))
            {
                    if(y.isLeftChild())
                    {
                            y.getParent().setLeftChild(x);
                    }
                    else
                    {
                            y.getParent().setRightChild(x);
                    }
            }
            else
            {
                    root=x;
            }
            x.setLeftChild(y);
            y.setRightChild(b);


    }

    /**
        * Rotates the subtree of the given tree right around that tree.
        * 
        * @param tree
        *            The tree to rotate around.
        */
    protected void rotateRight(TreeImpl tree) throws TreeErrorException {
            
            TreeImpl x=tree;
            TreeImpl y=x.getLeftChild();
            TreeImpl b = y.getRightChild();
            y.setParent(x.getParent());
            if(!(x.isRoot()))
            {
                    if(x.isLeftChild())
                    {
                            x.getParent().setLeftChild(y);
                    }
                    else
                    {
                            x.getParent().setRightChild(y);
                    }
            }
            else
            {
                    root=y;
            }
            y.setRightChild(x);
            x.setLeftChild(b);

    }
    
    public String toString(){
        return rbTree.toString();
    }

}
